
//三、实验内容
//编写程序完成如下几种排序算法，实现数据的从小到大的排序处理。
//（1）直接插入排序；
//（2）折半插入排序；
//（3）冒泡排序；
//（4）简单选择排序；
//（5）退出。
//要求：
//1.分别编写直接插入排序、折半插入排序、冒泡排序、简单选择排序几种排序算法的子函数，
//在主函数中通过调用各个子函数完成相应的排序任务。
//2. 设计一个菜单，选择不同的菜单项进行相应的排序操作，并给出按从小到大排好序的序列。
//3.分析并比较直接插入排序、折半插入排序、冒泡排序、简单选择排序几种排序算法的时间复杂度、空间复杂度以及稳定性。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

// 打印数组
void printArray(double arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%.2lf ", arr[i]);  // 保留两位小数输出，可按需调整格式
    }
    printf("\n");
}

// 直接插入排序（升序）
void insertionSortAsc(double arr[], int n) {
    int i, j;
    double key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
        printf("第 %d 趟直接插入排序（升序）结果: ", i);
        printArray(arr, n);
    }
}

// 直接插入排序（降序）
void insertionSortDesc(double arr[], int n) {
    int i, j;
    double key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] < key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
        printf("第 %d 趟直接插入排序（降序）结果: ", i);
        printArray(arr, n);
    }
}

// 折半插入排序（升序）
void binaryInsertionSortAsc(double arr[], int n) {
    int i, j, low, high, mid;
    double key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < arr[mid]) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high + 1; j--) {
            arr[j + 1] = arr[j];
        }
        arr[high + 1] = key;
        printf("第 %d 趟折半插入排序（升序）结果: ", i);
        printArray(arr, n);
    }
}

// 折半插入排序（降序）
void binaryInsertionSortDesc(double arr[], int n) {
    int i, j, low, high, mid;
    double key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key > arr[mid]) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high + 1; j--) {
            arr[j + 1] = arr[j];
        }
        arr[high + 1] = key;
        printf("第 %d 趟折半插入排序（降序）结果: ", i);
        printArray(arr, n);
    }
}

// 冒泡排序（升序）
void bubbleSortAsc(double arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                double temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        printf("第 %d 趟冒泡排序（升序）结果: ", i + 1);
        printArray(arr, n);
    }
}

// 冒泡排序（降序）
void bubbleSortDesc(double arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                double temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        printf("第 %d 趟冒泡排序（降序）结果: ", i + 1);
        printArray(arr, n);
    }
}

// 简单选择排序（升序）
void selectionSortAsc(double arr[], int n) {
    int i, j;
    int min_idx;
    double temp;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
        printf("第 %d 趟简单选择排序（升序）结果: ", i + 1);
        printArray(arr, n);
    }
}

// 简单选择排序（降序）
void selectionSortDesc(double arr[], int n) {
    int i, j;
    int max_idx;
    double temp;
    for (i = 0; i < n - 1; i++) {
        max_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] > arr[max_idx]) {
                max_idx = j;
            }
        }
        if (max_idx != i) {
            temp = arr[i];
            arr[i] = arr[max_idx];
            arr[max_idx] = temp;
        }
        printf("第 %d 趟简单选择排序（降序）结果: ", i + 1);
        printArray(arr, n);
    }
}

// 希尔排序（升序）
void shellSortAsc(double arr[], int n) {
    int gap, i, j;
    double key;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            key = arr[i];
            j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
            printf("第 %d 趟希尔排序（升序）结果（gap = %d）: ", i, gap);
            printArray(arr, n);
        }
    }
}

// 希尔排序（降序）
void shellSortDesc(double arr[], int n) {
    int gap, i, j;
    double key;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            key = arr[i];
            j = i;
            while (j >= gap && arr[j - gap] < key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
            printf("第 %d 趟希尔排序（降序）结果（gap = %d）: ", i, gap);
            printArray(arr, n);
        }
    }
}

// 调整最大堆（用于升序堆排序）
void maxHeapify(double arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        double swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        maxHeapify(arr, n, largest);
    }
}

// 调整最小堆（用于降序堆排序）
void minHeapify(double arr[], int n, int i) {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] < arr[smallest])
        smallest = l;
    if (r < n && arr[r] < arr[smallest])
        smallest = r;

    if (smallest != i) {
        double swap = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = swap;
        minHeapify(arr, n, smallest);
    }
}

// 堆排序（升序）
void heapSortAsc(double arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        double temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        maxHeapify(arr, i, 0);
        printf("第 %d 趟堆排序（升序）结果: ", n - i);
        printArray(arr, n);
    }
}

// 堆排序（降序）
void heapSortDesc(double arr[], int n) {
    // 构建最小堆
    for (int i = n / 2 - 1; i >= 0; i--)
        minHeapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        double temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        minHeapify(arr, i, 0);
        printf("第 %d 趟堆排序（降序）结果: ", n - i);
        printArray(arr, n);
    }
}

// 检查输入是否为合法的数字（整数或小数）
int isNumber(const char* str) {
    int dot_count = 0;
    int i = 0;
    if (str[0] == '-' || str[0] == '+')
        i = 1;
    for (; str[i] != '\0'; i++) {
        if (!isdigit(str[i])) {
            if (str[i] == '.' && dot_count == 0) {
                dot_count++;
            }
            else {
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    double arr[100];
    int n;
    int choice, order;
    // 获取数组元素个数，进行合法性检查
    while (1) {
        printf("请输入数组的元素个数：");
        char num_str[100];
        scanf("%s", num_str);
        if (isNumber(num_str)) {
            n = atoi(num_str);
            if (n > 0 && n <= 100) {
                break;
            }
            else {
                printf("输入的元素个数不在有效范围内（1 - 100），请重新输入。\n");
            }
        }
        else {
            printf("请输入合法数字作为元素个数，重新输入。\n");
        }
    }

    // 获取数组元素，进行合法性检查
    printf("请输入数组的元素：\n");
    for (int i = 0; i < n; i++) {
        while (1) {
            char element_str[100];
            scanf("%s", element_str);
            if (isNumber(element_str)) {
                arr[i] = atof(element_str);  // 将合法的数字字符串转换为double类型
                break;
            }
            else {
                printf("请输入合法数字作为数组元素，重新输入第 %d 个元素：", i + 1);
            }
        }
    }

    // 菜单
    while (1) {
        printf("\n请选择排序算法：\n");
        printf("1. 直接插入排序\n");
        printf("2. 折半插入排序\n");
        printf("3. 冒泡排序\n");
        printf("4. 简单选择排序\n");
        printf("5. 希尔排序\n");
        printf("6. 堆排序\n");
        printf("7. 退出\n");
        printf("请输入你的选择：");
        scanf("%d", &choice);

        printf("\n请选择排序顺序：\n");
        printf("1. 升序\n");
        printf("2. 降序\n");
        printf("请输入你的选择：");
        scanf("%d", &order);

        switch (choice) {
        case 1:
            if (order == 1)
                insertionSortAsc(arr, n);
            else
                insertionSortDesc(arr, n);
            break;
        case 2:
            if (order == 1)
                binaryInsertionSortAsc(arr, n);
            else
                binaryInsertionSortDesc(arr, n);
            break;
        case 3:
            if (order == 1)
                bubbleSortAsc(arr, n);
            else
                bubbleSortDesc(arr, n);
            break;
        case 4:
            if (order == 1)
                selectionSortAsc(arr, n);
            else
                selectionSortDesc(arr, n);
            break;
        case 5:
            if (order == 1)
                shellSortAsc(arr, n);
            else
                shellSortDesc(arr, n);
            break;
        case 6:
            if (order == 1)
                heapSortAsc(arr, n);
            else
                heapSortDesc(arr, n);
            break;
        case 7:
            printf("退出程序...\n");
            return 0;
        default:
            printf("无效选择，请重新输入。\n");
        }

        if (choice >= 1 && choice <= 6) {
            printf("最终排序结果：");
            printArray(arr, n);
        }
    }

    return 0;
}
